import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;

public class Solution {
    public static void main(String[] args) {
        Solution s = new Solution();
        int[] price = new int[]{2,2,2,2,2};
//        for(int e: s.twoSum(price, 18)) {
//            System.out.print(e + " ");
//        }
        s.fourSum(price, 8);
    }

    public int[] twoSum(int[] price, int target) {
        /**
         * 两数之和*/
        // 1 预处理
        int n = price.length;

        // 2 执行逻辑
        int l = 0;
        int r = n - 1;
        while(l < r) {
            if(price[l] + price[r] > target) {
                r--;
            } else if(price[l] + price[r] < target) {
                l++;
            } else {
                return new int[]{price[l], price[r]};
            }
        }

        // 3 返回值
        return null;
    }

    public List<List<Integer>> fourSum(int[] nums, int target) {
        /**
         * 四数之和
         * 要求：
         *  找到所有不重复的 元素和为target的四元组
         * 解题思路：
         *  固定2双指针找2*/
        // 1 预处理
        int n = nums.length;
        Arrays.sort(nums);
        List<List<Integer>> retList = new LinkedList<>();

        // 2 执行逻辑
        for(int i = 0; i < n-3; i++) {
            for(int j = i+1; j < n-2; j++) {
                // -新目标值
                long newTarget = (long)target - nums[i] - nums[j];
                int l = j+1;
                int r = n-1;
                while(l < r) {
                    if(nums[l] + nums[r] > newTarget) {
                        r--;
                    } else if(nums[l] + nums[r] < newTarget) {
                        l++;
                    } else {
                        List<Integer> tempList = new LinkedList<>();
                        tempList.add(nums[i]);
                        tempList.add(nums[j]);
                        tempList.add(nums[l]);
                        tempList.add(nums[r]);
                        if(!retList.contains(tempList)) {
                            retList.add(tempList);
                        }
                        // -因为是找到所有四元组，故此处推出可能会有遗漏
                        l++;
                    }
                }
            }
        }

        // 3 返回值
        return retList;
    }


}
